Images, particularly color images, contain a very large amount of information. This vary large amount of information makes it difficult to store or transmit such images, so high-performance encoding is used to reduce the amount of such data, either by deleting the redundancy of such color images or by encoding the images by altering their contents to the point where picture quality deteriorates noticeably. Thus, for example, with the JPEG recommended by the ISO and ITU-T as the international standard encoding method for data compression and decompression of still images, a discrete cosine transform (DCT) is used to transform each block of image data (8 pixels×8 pixels) into a DCT coefficient, after which the resulting DCT coefficients are individually quantized and the quantized values are entropy encoded to compress the image data. Besides JPEG, this DCT-based compression technique includes H261, MPEG1/2/4, and so on.
One process relating to DCT and to image data conversion is the Hadamard transform. The Hadamard transform is an orthogonal transformation in which each of the elements or entries in the matrix is either 1 or −1. A Hadamard transform can be performed using only addition and subtraction, and is the simplest of orthogonal transformations.
Within the Hadamard transform, a 2-point Hadamard transform matrix H2 is defined as follows:
                              H          2                =                              1                          2                                ⁡                      [                                                            1                                                  1                                                                              1                                                                      -                    1                                                                        ]                                              (        1        )            
An ordinary N-term Hadamard transform matrix HN (where N=2n) can be recursively defined by the Kronecker product of an (N/2)-term Hadamard transformation and the foregoing 2-point Hadamard transformation H2 as follows:
                                                                        H                N                            =                                                H                                      N                    /                    2                                                  -                                  H                  2                                                                                                        =                                                1                                      2                                                  ⁡                                  [                                                                                                              H                                                      W                            /                            2                                                                                                                                                H                                                      W                            /                            2                                                                                                                                                                                        H                                                      W                            /                            2                                                                                                                                                -                                                      H                                                          W                              /                              2                                                                                                                                                            ]                                                                                        (        2        )            
From the foregoing definition a 4-point Hadamard transform matrix can be obtained as follows:
                              H          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                                                1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                      ]                                              (        3        )            
Such a 4-point Hadamard transform matrix is called a natural matrix, in which the base vectors are not aligned in the order of the sequency. By repeatedly performing permutations of the base vectors so as to move the second line base vector to the forth line, the order of the base vectors becomes the sequence order of the transformation matrix WH4:
                              WH          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                        ]                                              (        4        )            
This transformation matrix WH4 is called a Walsh-type transformation matrix or a Walsh-Hadamard transform matrix. It is known that a Hadamard transform is a reversible orthogonal transformation, so as long as either the natural- or the Walsh-type matrix can be reversibly transformed the transformation matrix is a symmetrical matrix.
Besides the Walsh-type transformation matrix, there is one other type of symmetrical matrix obtained by permutation the base vectors of the Hadamard transform matrix H4, which is the following matrix HH4:
                              HH          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                                      -                    1                                                                                        -                    1                                                                    1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                                                1                                                  1                                                                      -                    1                                                                                        -                    1                                                                        ]                                              (        5        )            
This transform matrix HH4 has an important meaning in the detailed description of the invention that follows later.
As noted above, it is widely known that the Hadamard transform is reversible, a precondition of which is the retention without rounding of the decimal fraction generated when performing a Hadamard transformation of whole numbers (integers).
Reversibility is lost if the decimal fraction is simply rounded off. For example, a Hadamard transform of the following numbers                123, 78, 84, 56produces the following results:        170.5(=(123+78+84+56)/2)        36.5(=(123−78+84−56)/2)        30.5(=(123+78−84−56)/2)        8.5(=(123−78−84+56)/2)        
Rounding these numbers to integers yields the following:                171, 37, 31, 9the inverse transformation of which yields the following:        124, 78, 84, 56        
As can be seen, the first number 123, by a Hadamard transformation and its inverse transformation, has become 124. Thus, reversibility cannot be guaranteed with the Hadamard transform, which outputs integerized data. Hereinafter, a Hadamard transform that outputs integerized data is called an integer-type Hadamard transformation, and an integer-type Hadamard transformation that can be reversibly transformed is called an integer-type reversible Hadamard transformation.
The present invention is directed to a method of calculating and rounding so as to achieve an integer-type reversible Hadamard transformation.
Conventionally, an integer-type reversible Hadamard transformation is achieved as follows:                (1) Resolve the 4-point Hadamard transform H4 into the product of triangular matrixes whose main diagonal elements are equal to 1        (2) Add a row vector replacing Q to the original transformation matrix        (3) From (1) and (2), resolve QH4 into the following matrix product form.        
                              QH          4                =                                            [                                                                    1                                                        0                                                        0                                                        0                                                                                        0                                                        1                                                        0                                                        0                                                                                        0                                                                              -                      1                                                                            1                                                        0                                                                                                              -                      1                                                                            0                                                        0                                                        1                                                              ]                        ⁡                          [                                                                    1                                                        0                                                                              1                      /                      2                                                                                                  1                      /                      2                                                                                                            0                                                        1                                                                              1                      /                      2                                                                                                                          -                        1                                            /                      2                                                                                                            0                                                        0                                                        1                                                        0                                                                                        0                                                        0                                                        0                                                        1                                                              ]                                ⁡                      [                                                                                -                    1                                                                    0                                                  0                                                  0                                                                              0                                                                      -                    1                                                                    0                                                  0                                                                              1                                                  0                                                  1                                                  0                                                                              0                                                                      -                    1                                                                    0                                                  1                                                      ]                                              (        6        )                            (4) Express this transformation as signal flow (as shown in FIG. 1)        (5) Round off any decimal fraction data generated by multiplication during signal flow.        
Conventionally, an integer-type reversible Hadamard transformation is achieved by the foregoing steps (1) through (5). A slightly more detailed explanation is given below.
FIG. 1 is a diagram illustrating a signal flow that forms the foundations of achieving a conventional integer-type reversible Hadamard transformation. FIG. 2 is a diagram illustrating the signal flow of the conventional integer-type reversible Hadamard transformation.
The signal flow of FIG. 1 shows a so-called ladder network often used to achieve a reversible transformation. The ladder network shown in FIG. 1 introduces rounding (reference numerals 200 and 201 of FIG. 2) to the nearest integer on the output side of multipliers 100, 101 that generate decimal fraction data, with the reversibility of the transformation that outputs integerized data being used as a common technique (in the field of reversible transformation).
It should be noted that the methods of the rounding 200, 201 can be anything provided that the rounding of the corresponding multiplier outputs is the same for the forward transformation and the inverse transformation.
A signal flow that introduces rounding into the signal flow of FIG. 1 so as to achieve reversibility is shown in FIG. 2, and is the conventional calculation method for achieving an integer-type reversible Hadamard transformation.
The Hadamard transformation defined by equations (3), (4) and (5) above can be achieved by regular addition and subtraction, and can be processed in parallel efficiently SIMD (Single Instruction stream Multiple Data stream)-type commands such as those provided on current CPUs. However, with the above-described conventional reversible transformation calculation method, it is difficult to process using SIMD-type commands and there are few calculations that can be performed in parallel.
In other words, it can be said that the conventional integer-type reversible Hadamard transformation is not suitable for high-speed processing on the personal computers that are now ubiquitous. Similarly, the hardware also experiences extended delays because of the increased number of calculations involved, lengthening the data pass.